package problem763;

import java.util.ArrayList;
import java.util.List;


//763.划分字母区间(更优解)
//https://leetcode.cn/problems/partition-labels/?envType=study-plan-v2&envId=top-100-liked


class Solution2 {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        int n = s.length();
        int[] index = new int[128];
        for(int i = 0; i<n; i++) {
            index[s.charAt(i)] = i;
        }
        int pre = 0, r = 0;
        for(int i = 0; i<n; ) {
            r = index[s.charAt(i)];
            for(int j = i; j<=r; j++) {
                r = Math.max(r, index[s.charAt(j)]);
            }
            list.add(r - pre + 1);
            i = r + 1;
            pre = i;
        }
        return list;
    }
}